package someTestExcemple.huaweiOd.container.tree.bfsOrDfs;
//华为OD机试 - 传递悄悄话 - 深度优先搜索dfs（Java 2025 A卷 200分）
//https://blog.csdn.net/guorui_java/article/details/146799837
import java.util.*;
/*本题采用两个主要算法
        层序遍历（BFS）：用于根据输入构建二叉树。
        层序遍历能够按照从上到下、从左到右的顺序逐层构建二叉树节点，非常适合将线性输入转换为树形结构。
        深度优先搜索（DFS）：用于计算从根节点到叶子节点的最长路径和。
        当悄悄话从根节点开始传递时，所有节点接收到信息的总时间取决于最长的传递路径。
        二叉树是问题本身的自然表示形式，能够直观地表达人员之间的层级关系和传递路径。
        队列适合进行层序遍历，因为它满足先进先出(FIFO)的特性，可以确保按层级顺序处理节点。
        递归DFS适合计算路径和，因为它可以轻松地访问所有可能的路径，并在回溯时累加节点值，找出最长的路径。*/
public class PassWhispers {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nodes = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        sc.close();
        TreeNode root =buildTree(nodes,0);
        int totalTime = calculateTotalTime(root);
        System.out.println(totalTime);
        
    }

    public static TreeNode buildTree(int[] arr, int index) {
        if (index >= arr.length || arr[index] == -1) {
            return null;
        }
        TreeNode node = new TreeNode(arr[index]);
        node.leftNode = buildTree(arr, 2 * index + 1);
        node.rightNode = buildTree(arr, 2 * index + 2);
        return node;
    }

    public static int calculateTotalTime(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if(root.leftNode != null) {
            root.leftNode.value += root.value;
        }
        if(root.rightNode != null) {
            root.rightNode.value += root.value;
        }
        if(root.leftNode == null && root.rightNode == null) {
            return root.value;
        }
        int leftTime = calculateTotalTime(root.leftNode);
        int rightTime = calculateTotalTime(root.leftNode);
        return root.value + Math.max(leftTime, rightTime);
    }
    public static class TreeNode {
        int value;
        TreeNode leftNode;
        TreeNode rightNode;
        public TreeNode(int val) {
            this.value = val;
            this.leftNode = null;
            this.rightNode = null;
        }
    }
}
